package com.mlh.sort;

public class InsertionSort {
    public static void main(String[] args) {
        int[]arr={53,17,78,9,45,65,87,32,345,7,67,1,1,1,1,1,1,1,45,6,7,8,5,3,-3};
        solve(arr);
        for (int temp:arr){
            System.out.println(temp);
        }
    }

    public static int[] solve(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            compare(arr,i);
        }
        return arr;
    }

    public static void compare(int[] arr,int index) {
        int temp=arr[index];//暂存该值
        int res;//该数最终会插入的位置
        for(res=index;res>0;res--){
            if(arr[res-1]>temp){
                //大于则调换位置
                arr[res]=arr[res-1];
            }else{
                //小于则找到插入的位置
                break;
            }
        }
        arr[res]=temp;
    }

}